The present invention relates to encoding or compressing information.
Compressing a signal or information vector involves representing the signal or information vector by less bits than is required to reproduce exactly the original signal or information vector. Often, compression involves the projection of the information vector upon a suitably chosen space, perhaps followed by quantization.
As an example, a discrete sequence with N components may be represented exactly by a weighted sum of N complex-valued discrete sinusoidal basis functions, the so-called Discrete Fourier Transform (DFT), where the weights are the DFT coefficients. If only a few of the DFT coefficients are relatively large in magnitude, then the original discrete sequence can be approximated by these large coefficients and setting the rest to zero. This is equivalent to a projection of the original sequence onto a space spanned by the sinusoidal basis functions corresponding to the large coefficients. Furthermore, these remaining DFT coefficients may be quantized, perhaps non-uniformly, where more bits are used to represent the larger (in magnitude) DFT coefficients than for the smaller (in magnitude) DFT coefficients.
It is common for digital images to be compressed according to algorithms standardized by the Joint Photographic Experts Group (JPEG). These algorithms utilize the so-called Discrete Cosine Transform (DCT) on block sizes of 8 by 8, where again the basis functions are sinusoidal in nature.
The DCT is popular because of its relatively simple computational complexity. However, better performance may be obtained by using the Karhunen-Loeve Transform (KLT). The coefficients used for expressing an information vector in terms of the basis functions for the KLT are uncorrelated, so that images with statistical correlation among its pixels can be accurately approximated (encoded or compressed) by the largest (in magnitude) KLT coefficients and their corresponding basis functions. The basis functions for the KLT are the eigenvectors of the auto-correlation matrix of the image to be compressed. However, this is computationally intensive, since both the auto-correlation matrix must be obtained (where it is assumed that the image is a stationary stochastic process during the time in which the auto-correlation matrix is estimated), and the eigenvectors of the matrix must be computed.
It is therefore desirable to obtain basis functions which provide compression similar to the KLT without its computational complexity.